package com.lun.swordtowardoffer2.c08;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class IncreasingBST {
	
	public TreeNode increaseBST(TreeNode root) {
		LinkedList<TreeNode> stack = new LinkedList<>();
		
		TreeNode cur = root;
		TreeNode first = null;
		TreeNode prev = null;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			}else {
				cur = stack.pop();
				
				if(prev == null) {
					first = cur; 					
				}else {
					prev.right = cur;
				}
				prev = cur;
				cur.left = null;
				
				cur = cur.right;
			}
		}
		
		return first;
	}
	
}
